🔢 Matrici in C: Guida Completa

Dalle basi agli algoritmi più avanzati - Diventa un esperto delle matrici

📑 Indice della Lezione

1. Introduzione alle Matrici

Una matrice è una struttura dati bidimensionale che organizza elementi in righe e colonne. In C, le matrici sono implementate come array di array.

💡 Concetti Fondamentali:
  • Matrice m×n: m righe e n colonne
  • Elemento aij: elemento alla riga i e colonna j
  • Matrice quadrata: m = n (stesso numero di righe e colonne)
  • Diagonale principale: elementi dove i = j
  • Matrice identità: diagonale = 1, resto = 0

Rappresentazione in Memoria

In C, le matrici sono memorizzate in modo row-major (per righe): gli elementi di ogni riga sono memorizzati consecutivamente in memoria. 

// Matrice 3×3
int mat[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// In memoria: [1][2][3][4][5][6][7][8][9]
// Indirizzo elemento mat[i][j] = base + (i * n_colonne + j) * sizeof(tipo)

2. Dichiarazione e Inizializzazione

2.1 Array Statici

#include <stdio.h>

int main(void) {
    // Dichiarazione semplice
    int mat1[3][4];  // Matrice 3×4 non inizializzata
    
    // Inizializzazione completa
    int mat2[2][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };
    
    // Inizializzazione parziale (il resto è 0)
    int mat3[3][3] = {
        {1, 2},    // {1, 2, 0}
        {3}        // {3, 0, 0}
                    // {0, 0, 0}
    };
    
    // Inizializzazione senza specificare la prima dimensione
    int mat4[][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };  // Il compilatore deduce che è 2×3
    
    // Inizializzazione a zero
    int mat_zero[3][3] = {0};  // Tutti gli elementi a 0
    
    // Accesso agli elementi
    mat1[0][0] = 10;
    int valore = mat2[1][2];  // valore = 6
    
    return 0;
}

2.2 Matrici come Parametri di Funzione

#include <stdio.h>

// Metodo 1: Dimensione fissa
void stampa_matrice_fissa(int mat[3][4]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
}

// Metodo 2: Numero colonne fisso, righe variabili
void stampa_matrice_variabile(int mat[][4], int righe) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
}

// Metodo 3: Array di puntatori (più flessibile)
void stampa_matrice_puntatori(int **mat, int righe, int colonne) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            printf("%d ", mat[i][j]);
        }
        printf("\n");
    }
}

// Metodo 4: Puntatore singolo (trattare come array 1D)
void stampa_matrice_flat(int *mat, int righe, int colonne) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            // Accesso: mat[i * colonne + j]
            printf("%d ", mat[i * colonne + j]);
        }
        printf("\n");
    }
}

3. Allocazione Dinamica

3.1 Metodo 1: Array Contiguo (Più Efficiente)

#include <stdio.h>
#include <stdlib.h>

/**
 * @brief Alloca una matrice come array contiguo
 * @return Puntatore alla matrice o NULL se errore
 */
int* crea_matrice_contigua(int righe, int colonne) {
    int *mat = (int*)malloc(righe * colonne * sizeof(int));
    
    if (mat == NULL) {
        fprintf(stderr, "Errore di allocazione memoria\n");
        return NULL;
    }
    
    // Inizializza a zero
    for (int i = 0; i < righe * colonne; i++) {
        mat[i] = 0;
    }
    
    return mat;
}

/**
 * @brief Accede a elemento mat[i][j]
 */
int get_elemento(int *mat, int i, int j, int colonne) {
    return mat[i * colonne + j];
}

void set_elemento(int *mat, int i, int j, int colonne, int valore) {
    mat[i * colonne + j] = valore;
}

void libera_matrice_contigua(int *mat) {
    free(mat);
}

3.2 Metodo 2: Array di Puntatori

/**
 * @brief Alloca matrice come array di puntatori
 * Ogni riga è un array separato
 */
int** crea_matrice_puntatori(int righe, int colonne) {
    // Alloca array di puntatori alle righe
    int **mat = (int**)malloc(righe * sizeof(int*));
    
    if (mat == NULL) {
        return NULL;
    }
    
    // Alloca ogni riga
    for (int i = 0; i < righe; i++) {
        mat[i] = (int*)malloc(colonne * sizeof(int));
        
        if (mat[i] == NULL) {
            // Libera memoria già allocata in caso di errore
            for (int j = 0; j < i; j++) {
                free(mat[j]);
            }
            free(mat);
            return NULL;
        }
        
        // Inizializza riga a zero
        for (int j = 0; j < colonne; j++) {
            mat[i][j] = 0;
        }
    }
    
    return mat;
}

void libera_matrice_puntatori(int **mat, int righe) {
    if (mat == NULL) return;
    
    for (int i = 0; i < righe; i++) {
        free(mat[i]);
    }
    free(mat);
}

3.3 Metodo 3: Singola Allocazione con Puntatori (Ottimizzato)

/**
 * @brief Alloca matrice con singola malloc ma accesso tramite puntatori
 * Combina efficienza del metodo 1 con comodità del metodo 2
 */
int** crea_matrice_ottimizzata(int righe, int colonne) {
    // Alloca tutto in un blocco unico
    int **mat = (int**)malloc(righe * sizeof(int*) + 
                                righe * colonne * sizeof(int));
    
    if (mat == NULL) {
        return NULL;
    }
    
    // I dati iniziano dopo l'array di puntatori
    int *dati = (int*)(mat + righe);
    
    // Imposta i puntatori alle righe
    for (int i = 0; i < righe; i++) {
        mat[i] = dati + i * colonne;
    }
    
    // Inizializza a zero
    for (int i = 0; i < righe * colonne; i++) {
        dati[i] = 0;
    }
    
    return mat;
}

void libera_matrice_ottimizzata(int **mat) {
    free(mat);  // Una singola free!
}
📊 Confronto Metodi di Allocazione:
Metodo Memoria Contigua Sintassi mat[i][j] Performance Chiamate malloc
Array Contiguo ✅ Sì ❌ No ⭐⭐⭐ 1
Array di Puntatori ❌ No ✅ Sì ⭐⭐ n+1
Ottimizzato ✅ Sì ✅ Sì ⭐⭐⭐ 1

4. Operazioni di Base

4.1 Stampa e Input

#include <stdio.h>

/**
 * @brief Stampa una matrice in formato leggibile
 */
void stampa_matrice(int **mat, int righe, int colonne) {
    printf("\n");
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            printf("%6d ", mat[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

/**
 * @brief Legge matrice da input utente
 */
void leggi_matrice(int **mat, int righe, int colonne) {
    printf("Inserisci gli elementi della matrice %dx%d:\n", righe, colonne);
    
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            printf("Elemento [%d][%d]: ", i, j);
            scanf("%d", &mat[i][j]);
        }
    }
}

/**
 * @brief Inizializza matrice con valori casuali
 */
void riempi_casuale(int **mat, int righe, int colonne, int max) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            mat[i][j] = rand() % max;
        }
    }
}

4.2 Somma e Sottrazione

/**
 * @brief Somma due matrici: C = A + B
 * @return true se successo, false se dimensioni incompatibili
 */
bool somma_matrici(int **A, int **B, int **C, 
                   int righe, int colonne) {
    if (A == NULL || B == NULL || C == NULL) {
        return false;
    }
    
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
    
    return true;
}

/**
 * @brief Sottrazione di matrici: C = A - B
 */
bool sottrai_matrici(int **A, int **B, int **C,
                      int righe, int colonne) {
    if (A == NULL || B == NULL || C == NULL) {
        return false;
    }
    
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
    
    return true;
}

/**
 * @brief Moltiplicazione per scalare: B = k * A
 */
void moltiplica_scalare(int **A, int **B, int k,
                        int righe, int colonne) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            B[i][j] = k * A[i][j];
        }
    }
}

4.3 Prodotto di Matrici

/**
 * @brief Prodotto di matrici: C = A × B
 * A è m×n, B è n×p, C è m×p
 * Complessità: O(m × n × p)
 */
bool moltiplica_matrici(int **A, int **B, int **C,
                        int m, int n, int p) {
    if (A == NULL || B == NULL || C == NULL) {
        return false;
    }
    
    // Inizializza C a zero
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
        }
    }
    
    // Prodotto: C[i][j] = Σ(A[i][k] * B[k][j]) per k da 0 a n-1
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    
    return true;
}

/**
 * @brief Prodotto ottimizzato (cache-friendly)
 * Migliore località spaziale
 */
bool moltiplica_matrici_ottimizzato(int **A, int **B, int **C,
                                     int m, int n, int p) {
    // Inizializza C
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
        }
    }
    
    // Scambia ordine dei loop per migliorare cache hit
    for (int i = 0; i < m; i++) {
        for (int k = 0; k < n; k++) {
            int temp = A[i][k];
            for (int j = 0; j < p; j++) {
                C[i][j] += temp * B[k][j];
            }
        }
    }
    
    return true;
}

4.4 Trasposizione

/**
 * @brief Traspone una matrice: B = A^T
 * Se A è m×n, B è n×m
 */
void trasponi_matrice(int **A, int **B, int righe, int colonne) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < colonne; j++) {
            B[j][i] = A[i][j];
        }
    }
}

/**
 * @brief Traspone matrice quadrata in-place
 */
void trasponi_in_place(int **mat, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Scambia mat[i][j] con mat[j][i]
            int temp = mat[i][j];
            mat[i][j] = mat[j][i];
            mat[j][i] = temp;
        }
    }
}

5. Operazioni Avanzate

5.1 Determinante (Algoritmo Ricorsivo)

/**
 * @brief Calcola il determinante di una matrice quadrata
 * Usa sviluppo di Laplace (ricorsivo)
 * Complessità: O(n!)
 */
int determinante(int **mat, int n) {
    // Caso base: matrice 1×1
    if (n == 1) {
        return mat[0][0];
    }
    
    // Caso base: matrice 2×2
    if (n == 2) {
        return mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0];
    }
    
    int det = 0;
    
    // Alloca sottomatrice (n-1)×(n-1)
    int **submat = crea_matrice_puntatori(n - 1, n - 1);
    
    // Sviluppo lungo la prima riga
    for (int x = 0; x < n; x++) {
        // Crea sottomatrice escludendo riga 0 e colonna x
        int sub_i = 0;
        for (int i = 1; i < n; i++) {
            int sub_j = 0;
            for (int j = 0; j < n; j++) {
                if (j == x) continue;
                submat[sub_i][sub_j++] = mat[i][j];
            }
            sub_i++;
        }
        
        // Formula: det = Σ((-1)^j * a[0][j] * det(submat))
        int segno = (x % 2 == 0) ? 1 : -1;
        det += segno * mat[0][x] * determinante(submat, n - 1);
    }
    
    libera_matrice_puntatori(submat, n - 1);
    
    return det;
}

/**
 * @brief Calcola determinante con eliminazione di Gauss
 * Complessità: O(n³) - molto più efficiente!
 */
double determinante_gauss(double **mat, int n) {
    // Crea copia della matrice
    double **temp = (double**)malloc(n * sizeof(double*));
    for (int i = 0; i < n; i++) {
        temp[i] = (double*)malloc(n * sizeof(double));
        for (int j = 0; j < n; j++) {
            temp[i][j] = mat[i][j];
        }
    }
    
    double det = 1.0;
    
    // Eliminazione gaussiana
    for (int i = 0; i < n; i++) {
        // Trova pivot
        int max_row = i;
        for (int k = i + 1; k < n; k++) {
            if (fabs(temp[k][i]) > fabs(temp[max_row][i])) {
                max_row = k;
            }
        }
        
        // Scambia righe se necessario
        if (max_row != i) {
            double *tmp = temp[i];
            temp[i] = temp[max_row];
            temp[max_row] = tmp;
            det = -det;  // Cambio di segno
        }
        
        // Se pivot è zero, det = 0
        if (fabs(temp[i][i]) < 1e-10) {
            det = 0;
            break;
        }
        
        // Elimina colonna sotto il pivot
        for (int k = i + 1; k < n; k++) {
            double factor = temp[k][i] / temp[i][i];
            for (int j = i; j < n; j++) {
                temp[k][j] -= factor * temp[i][j];
            }
        }
        
        det *= temp[i][i];
    }
    
    // Libera memoria
    for (int i = 0; i < n; i++) {
        free(temp[i]);
    }
    free(temp);
    
    return det;
}

5.2 Matrice Inversa (Gauss-Jordan)

#include <math.h>

/**
 * @brief Calcola la matrice inversa usando Gauss-Jordan
 * @param mat Matrice da invertire (n×n)
 * @param inv Matrice inversa risultante (n×n)
 * @return true se la matrice è invertibile, false altrimenti
 */
bool matrice_inversa(double **mat, double **inv, int n) {
    // Crea matrice aumentata [mat | I]
    double **aug = (double**)malloc(n * sizeof(double*));
    for (int i = 0; i < n; i++) {
        aug[i] = (double*)malloc(2 * n * sizeof(double));
        for (int j = 0; j < n; j++) {
            aug[i][j] = mat[i][j];
            aug[i][n + j] = (i == j) ? 1.0 : 0.0;  // Matrice identità
        }
    }
    
    // Eliminazione di Gauss-Jordan
    for (int i = 0; i < n; i++) {
        // Trova pivot
        int max_row = i;
        for (int k = i + 1; k < n; k++) {
            if (fabs(aug[k][i]) > fabs(aug[max_row][i])) {
                max_row = k;
            }
        }
        
        // Scambia righe
        if (max_row != i) {
            double *tmp = aug[i];
            aug[i] = aug[max_row];
            aug[max_row] = tmp;
        }
        
        // Controlla se matrice è singolare
        if (fabs(aug[i][i]) < 1e-10) {
            // Libera memoria
            for (int k = 0; k < n; k++) free(aug[k]);
            free(aug);
            return false;
        }
        
        // Normalizza riga pivot
        double pivot = aug[i][i];
        for (int j = 0; j < 2 * n; j++) {
            aug[i][j] /= pivot;
        }
        
        // Elimina colonna in tutte le altre righe
        for (int k = 0; k < n; k++) {
            if (k != i) {
                double factor = aug[k][i];
                for (int j = 0; j < 2 * n; j++) {
                    aug[k][j] -= factor * aug[i][j];
                }
            }
        }
    }
    
    // Copia la parte destra (matrice inversa) in inv
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            inv[i][j] = aug[i][n + j];
        }
    }
    
    // Libera memoria
    for (int i = 0; i < n; i++) free(aug[i]);
    free(aug);
    
    return true;
}

6. Algoritmi Complessi

6.1 Decomposizione LU

/**
 * @brief Decomposizione LU: A = L × U
 * L è triangolare inferiore, U è triangolare superiore
 * Utile per risolvere sistemi lineari
 * Complessità: O(n³)
 */
bool decomposizione_LU(double **A, double **L, double **U, int n) {
    // Inizializza L e U
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            L[i][j] = (i == j) ? 1.0 : 0.0;
            U[i][j] = 0.0;
        }
    }
    
    // Algoritmo di Doolittle
    for (int i = 0; i < n; i++) {
        // Calcola riga i di U
        for (int j = i; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < i; k++) {
                sum += L[i][k] * U[k][j];
            }
            U[i][j] = A[i][j] - sum;
        }
        
        // Calcola colonna i di L
        for (int j = i + 1; j < n; j++) {
            if (fabs(U[i][i]) < 1e-10) {
                return false;  // Matrice singolare
            }
            
            double sum = 0.0;
            for (int k = 0; k < i; k++) {
                sum += L[j][k] * U[k][i];
            }
            L[j][i] = (A[j][i] - sum) / U[i][i];
        }
    }
    
    return true;
}

/**
 * @brief Risolve sistema Ax = b usando decomposizione LU
 * Prima risolve Ly = b, poi Ux = y
 */
void risolvi_LU(double **L, double **U, double *b, double *x, int n) {
    double *y = (double*)malloc(n * sizeof(double));
    
    // Forward substitution: Ly = b
    for (int i = 0; i < n; i++) {
        double sum = 0.0;
        for (int j = 0; j < i; j++) {
            sum += L[i][j] * y[j];
        }
        y[i] = (b[i] - sum) / L[i][i];
    }
    
    // Back substitution: Ux = y
    for (int i = n - 1; i >= 0; i--) {
        double sum = 0.0;
        for (int j = i + 1; j < n; j++) {
            sum += U[i][j] * x[j];
        }
        x[i] = (y[i] - sum) / U[i][i];
    }
    
    free(y);
}

6.2 Algoritmo di Strassen (Moltiplicazione Veloce)

/**
 * @brief Moltiplicazione di Strassen
 * Complessità: O(n^2.807) invece di O(n³)
 * Funziona per matrici di dimensione potenza di 2
 */
void somma_mat(int **A, int **B, int **C, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C[i][j] = A[i][j] + B[i][j];
        }
    }
}

void sottrai_mat(int **A, int **B, int **C, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C[i][j] = A[i][j] - B[i][j];
        }
    }
}

void strassen(int **A, int **B, int **C, int n) {
    // Caso base: matrice 1×1
    if (n == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }
    
    // Per matrici piccole, usa algoritmo standard
    if (n <= 64) {
        moltiplica_matrici(A, B, C, n, n, n);
        return;
    }
    
    int new_size = n / 2;
    
    // Alloca sottomatrici
    int **A11 = crea_matrice_puntatori(new_size, new_size);
    int **A12 = crea_matrice_puntatori(new_size, new_size);
    int **A21 = crea_matrice_puntatori(new_size, new_size);
    int **A22 = crea_matrice_puntatori(new_size, new_size);
    
    int **B11 = crea_matrice_puntatori(new_size, new_size);
    int **B12 = crea_matrice_puntatori(new_size, new_size);
    int **B21 = crea_matrice_puntatori(new_size, new_size);
    int **B22 = crea_matrice_puntatori(new_size, new_size);
    
    // Matrici per i prodotti intermedi M1-M7
    int **M1 = crea_matrice_puntatori(new_size, new_size);
    int **M2 = crea_matrice_puntatori(new_size, new_size);
    int **M3 = crea_matrice_puntatori(new_size, new_size);
    int **M4 = crea_matrice_puntatori(new_size, new_size);
    int **M5 = crea_matrice_puntatori(new_size, new_size);
    int **M6 = crea_matrice_puntatori(new_size, new_size);
    int **M7 = crea_matrice_puntatori(new_size, new_size);
    
    int **temp1 = crea_matrice_puntatori(new_size, new_size);
    int **temp2 = crea_matrice_puntatori(new_size, new_size);
    
    // Dividi matrici in 4 sottomatrici
    for (int i = 0; i < new_size; i++) {
        for (int j = 0; j < new_size; j++) {
            A11[i][j] = A[i][j];
            A12[i][j] = A[i][j + new_size];
            A21[i][j] = A[i + new_size][j];
            A22[i][j] = A[i + new_size][j + new_size];
            
            B11[i][j] = B[i][j];
            B12[i][j] = B[i][j + new_size];
            B21[i][j] = B[i + new_size][j];
            B22[i][j] = B[i + new_size][j + new_size];
        }
    }
    
    // Calcola i 7 prodotti di Strassen
    // M1 = (A11 + A22) × (B11 + B22)
    somma_mat(A11, A22, temp1, new_size);
    somma_mat(B11, B22, temp2, new_size);
    strassen(temp1, temp2, M1, new_size);
    
    // M2 = (A21 + A22) × B11
    somma_mat(A21, A22, temp1, new_size);
    strassen(temp1, B11, M2, new_size);
    
    // M3 = A11 × (B12 - B22)
    sottrai_mat(B12, B22, temp1, new_size);
    strassen(A11, temp1, M3, new_size);
    
    // M4 = A22 × (B21 - B11)
    sottrai_mat(B21, B11, temp1, new_size);
    strassen(A22, temp1, M4, new_size);
    
    // M5 = (A11 + A12) × B22
    somma_mat(A11, A12, temp1, new_size);
    strassen(temp1, B22, M5, new_size);
    
    // M6 = (A21 - A11) × (B11 + B12)
    sottrai_mat(A21, A11, temp1, new_size);
    somma_mat(B11, B12, temp2, new_size);
    strassen(temp1, temp2, M6, new_size);
    
    // M7 = (A12 - A22) × (B21 + B22)
    sottrai_mat(A12, A22, temp1, new_size);
    somma_mat(B21, B22, temp2, new_size);
    strassen(temp1, temp2, M7, new_size);
    
    // Combina i risultati
    // C11 = M1 + M4 - M5 + M7
    // C12 = M3 + M5
    // C21 = M2 + M4
    // C22 = M1 - M2 + M3 + M6
    
    for (int i = 0; i < new_size; i++) {
        for (int j = 0; j < new_size; j++) {
            C[i][j] = M1[i][j] + M4[i][j] - M5[i][j] + M7[i][j];
            C[i][j + new_size] = M3[i][j] + M5[i][j];
            C[i + new_size][j] = M2[i][j] + M4[i][j];
            C[i + new_size][j + new_size] = M1[i][j] - M2[i][j] + M3[i][j] + M6[i][j];
        }
    }
    
    // Libera memoria (codice di pulizia omesso per brevità)
}

6.3 Autovalori e Autovettori (Power Iteration)

/**
 * @brief Trova l'autovalore dominante e il suo autovettore
 * Usa il metodo della potenza
 */
double power_iteration(double **A, int n, double *autovettore, 
                       int max_iter, double tol) {
    // Inizializza autovettore casuale
    double *v = (double*)malloc(n * sizeof(double));
    double *v_new = (double*)malloc(n * sizeof(double));
    
    for (int i = 0; i < n; i++) {
        v[i] = (double)rand() / RAND_MAX;
    }
    
    // Normalizza
    double norm = 0.0;
    for (int i = 0; i < n; i++) {
        norm += v[i] * v[i];
    }
    norm = sqrt(norm);
    for (int i = 0; i < n; i++) {
        v[i] /= norm;
    }
    
    double autovalore = 0.0;
    
    // Iterazione
    for (int iter = 0; iter < max_iter; iter++) {
        // v_new = A × v
        for (int i = 0; i < n; i++) {
            v_new[i] = 0.0;
            for (int j = 0; j < n; j++) {
                v_new[i] += A[i][j] * v[j];
            }
        }
        
        // Calcola autovalore (Rayleigh quotient)
        double num = 0.0, den = 0.0;
        for (int i = 0; i < n; i++) {
            num += v[i] * v_new[i];
            den += v[i] * v[i];
        }
        double nuovo_autovalore = num / den;
        
        // Controlla convergenza
        if (fabs(nuovo_autovalore - autovalore) < tol) {
            autovalore = nuovo_autovalore;
            break;
        }
        
        autovalore = nuovo_autovalore;
        
        // Normalizza v_new
        norm = 0.0;
        for (int i = 0; i < n; i++) {
            norm += v_new[i] * v_new[i];
        }
        norm = sqrt(norm);
        
        for (int i = 0; i < n; i++) {
            v[i] = v_new[i] / norm;
        }
    }
    
    // Copia autovettore finale
    for (int i = 0; i < n; i++) {
        autovettore[i] = v[i];
    }
    
    free(v);
    free(v_new);
    
    return autovalore;
}

7. Matrici Sparse

Le matrici sparse contengono prevalentemente zeri. Memorizzarle in modo efficiente risparmia molta memoria.

7.1 Formato COO (Coordinate)

typedef struct {
    int riga;
    int colonna;
    double valore;
} ElementoSparse;

typedef struct {
    ElementoSparse *elementi;
    int num_elementi;
    int righe;
    int colonne;
    int capacita;
} MatriceSparse;

/**
 * @brief Crea matrice sparse
 */
MatriceSparse* crea_matrice_sparse(int righe, int colonne, int capacita) {
    MatriceSparse *mat = (MatriceSparse*)malloc(sizeof(MatriceSparse));
    mat->elementi = (ElementoSparse*)malloc(capacita * sizeof(ElementoSparse));
    mat->num_elementi = 0;
    mat->righe = righe;
    mat->colonne = colonne;
    mat->capacita = capacita;
    return mat;
}

/**
 * @brief Inserisce elemento nella matrice sparse
 */
void inserisci_sparse(MatriceSparse *mat, int i, int j, double valore) {
    if (valore == 0.0) return;  // Non memorizzare zeri
    
    if (mat->num_elementi >= mat->capacita) {
        // Espandi capacità
        mat->capacita *= 2;
        mat->elementi = (ElementoSparse*)realloc(mat->elementi, 
                                                mat->capacita * sizeof(ElementoSparse));
    }
    
    mat->elementi[mat->num_elementi].riga = i;
    mat->elementi[mat->num_elementi].colonna = j;
    mat->elementi[mat->num_elementi].valore = valore;
    mat->num_elementi++;
}

/**
 * @brief Ottiene elemento dalla matrice sparse
 */
double get_sparse(MatriceSparse *mat, int i, int j) {
    for (int k = 0; k < mat->num_elementi; k++) {
        if (mat->elementi[k].riga == i && mat->elementi[k].colonna == j) {
            return mat->elementi[k].valore;
        }
    }
    return 0.0;  // Elemento non trovato = zero
}

/**
 * @brief Prodotto matrice sparse per vettore
 * y = A × x
 */
void moltiplica_sparse_vettore(MatriceSparse *A, double *x, double *y) {
    // Inizializza y a zero
    for (int i = 0; i < A->righe; i++) {
        y[i] = 0.0;
    }
    
    // Moltiplica solo elementi non-zero
    for (int k = 0; k < A->num_elementi; k++) {
        int i = A->elementi[k].riga;
        int j = A->elementi[k].colonna;
        double val = A->elementi[k].valore;
        
        y[i] += val * x[j];
    }
}

8. Ottimizzazione e Performance

8.1 Loop Tiling (Blocchi per Cache)

/**
 * @brief Prodotto matrici con loop tiling per migliorare cache hit
 * Divide matrici in blocchi che si adattano alla cache
 */
void moltiplica_tiled(double **A, double **B, double **C, 
                     int n, int block_size) {
    // Inizializza C
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C[i][j] = 0.0;
        }
    }
    
    // Loop sui blocchi
    for (int ii = 0; ii < n; ii += block_size) {
        for (int jj = 0; jj < n; jj += block_size) {
            for (int kk = 0; kk < n; kk += block_size) {
                // Loop all'interno del blocco
                for (int i = ii; i < ii + block_size && i < n; i++) {
                    for (int k = kk; k < kk + block_size && k < n; k++) {
                        double temp = A[i][k];
                        for (int j = jj; j < jj + block_size && j < n; j++) {
                            C[i][j] += temp * B[k][j];
                        }
                    }
                }
            }
        }
    }
}

8.2 Trasposizione Ottimizzata

/**
 * @brief Trasposizione ottimizzata con blocchi
 */
void trasponi_ottimizzata(double **src, double **dst, 
                          int n, int block_size) {
    for (int ii = 0; ii < n; ii += block_size) {
        for (int jj = 0; jj < n; jj += block_size) {
            for (int i = ii; i < ii + block_size && i < n; i++) {
                for (int j = jj; j < jj + block_size && j < n; j++) {
                    dst[j][i] = src[i][j];
                }
            }
        }
    }
}

9. Esercizi Progressivi

💪 Esercizio 1: Matrice Identità FACILE

Obiettivo: Crea una funzione che genera una matrice identità di dimensione n×n.

Input: Dimensione n

Output: Matrice identità (1 sulla diagonale, 0 altrove)

Soluzione:

void crea_identita(int **mat, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] = (i == j) ? 1 : 0;
        }
    }
}

💪 Esercizio 2: Rotazione 90° FACILE

Obiettivo: Ruota una matrice quadrata di 90° in senso orario.

Suggerimento: Prima trasponi, poi inverti ogni riga.

Soluzione:

void ruota_90_orario(int **mat, int n) {
    // Trasponi
    trasponi_in_place(mat, n);
    
    // Inverti ogni riga
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int temp = mat[i][j];
            mat[i][j] = mat[i][n - 1 - j];
            mat[i][n - 1 - j] = temp;
        }
    }
}

💪 Esercizio 3: Spirale MEDIO

Obiettivo: Riempi una matrice n×n con numeri da 1 a n² in senso spirale (orario dall'esterno).

Soluzione:

void riempi_spirale(int **mat, int n) {
    int top = 0, bottom = n - 1;
    int left = 0, right = n - 1;
    int num = 1;
    
    while (top <= bottom && left <= right) {
        // Destra
        for (int j = left; j <= right; j++) {
            mat[top][j] = num++;
        }
        top++;
        
        // Giù
        for (int i = top; i <= bottom; i++) {
            mat[i][right] = num++;
        }
        right--;
        
        // Sinistra
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                mat[bottom][j] = num++;
            }
            bottom--;
        }
        
        // Su
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                mat[i][left] = num++;
            }
            left++;
        }
    }
}

💪 Esercizio 4: Traccia del Prodotto MEDIO

Obiettivo: Calcola la traccia di A×B senza calcolare l'intera matrice prodotto.

Formula: Tr(A×B) = Σi,j A[i][j] × B[j][i]

Soluzione:

double traccia_prodotto(double **A, double **B, int n) {
    double traccia = 0.0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            traccia += A[i][j] * B[j][i];
        }
    }
    
    return traccia;
}

💪 Esercizio 5: Sottomatrice con Somma Massima DIFFICILE

Obiettivo: Trova la sottomatrice rettangolare con somma massima.

Algoritmo: Usa Kadane 2D - complessità O(n³)

Soluzione:

// Kadane 1D per trovare subarray con somma massima
int kadane_1d(int *arr, int n, int *start, int *end) {
    int max_sum = arr[0];
    int current_sum = arr[0];
    *start = 0;
    *end = 0;
    int temp_start = 0;
    
    for (int i = 1; i < n; i++) {
        if (current_sum < 0) {
            current_sum = arr[i];
            temp_start = i;
        } else {
            current_sum += arr[i];
        }
        
        if (current_sum > max_sum) {
            max_sum = current_sum;
            *start = temp_start;
            *end = i;
        }
    }
    
    return max_sum;
}

// Kadane 2D
int sottomatrice_massima(int **mat, int m, int n,
                        int *top, int *left, int *bottom, int *right) {
    int max_sum = INT_MIN;
    int *temp = (int*)malloc(m * sizeof(int));
    
    // Prova tutte le coppie di colonne
    for (int col_left = 0; col_left < n; col_left++) {
        // Inizializza temp
        for (int i = 0; i < m; i++) {
            temp[i] = 0;
        }
        
        for (int col_right = col_left; col_right < n; col_right++) {
            // Aggiungi colonna corrente a temp
            for (int i = 0; i < m; i++) {
                temp[i] += mat[i][col_right];
            }
            
            // Trova max subarray in temp
            int start, end;
            int sum = kadane_1d(temp, m, &start, &end);
            
            if (sum > max_sum) {
                max_sum = sum;
                *top = start;
                *bottom = end;
                *left = col_left;
                *right = col_right;
            }
        }
    }
    
    free(temp);
    return max_sum;
}

💪 Esercizio 6: Rango di una Matrice DIFFICILE

Obiettivo: Calcola il rango di una matrice usando eliminazione gaussiana.

Soluzione:

int calcola_rango(double **mat, int m, int n) {
    // Crea copia della matrice
    double **temp = (double**)malloc(m * sizeof(double*));
    for (int i = 0; i < m; i++) {
        temp[i] = (double*)malloc(n * sizeof(double));
        for (int j = 0; j < n; j++) {
            temp[i][j] = mat[i][j];
        }
    }
    
    int rango = 0;
    double epsilon = 1e-10;
    
    for (int col = 0; col < n && rango < m; col++) {
        // Trova pivot
        int pivot_row = -1;
        for (int i = rango; i < m; i++) {
            if (fabs(temp[i][col]) > epsilon) {
                pivot_row = i;
                break;
            }
        }
        
        // Se nessun pivot, passa alla colonna successiva
        if (pivot_row == -1) continue;
        
        // Scambia righe
        if (pivot_row != rango) {
            double *tmp = temp[rango];
            temp[rango] = temp[pivot_row];
            temp[pivot_row] = tmp;
        }
        
        // Elimina colonna sotto il pivot
        for (int i = rango + 1; i < m; i++) {
            double factor = temp[i][col] / temp[rango][col];
            for (int j = col; j < n; j++) {
                temp[i][j] -= factor * temp[rango][j];
            }
        }
        
        rango++;
    }
    
    // Libera memoria
    for (int i = 0; i < m; i++) free(temp[i]);
    free(temp);
    
    return rango;
}

💪 Esercizio 7: Ricerca Percorso in Labirinto DIFFICILE

Obiettivo: Data una matrice che rappresenta un labirinto (0=libero, 1=muro), trova il percorso più breve da (0,0) a (n-1,n-1).

Algoritmo: BFS (Breadth-First Search)

Soluzione:

#include <stdbool.h>

typedef struct {
    int x, y;
    int dist;
} Punto;

int trova_percorso_labirinto(int **labirinto, int n) {
    if (labirinto[0][0] == 1 || labirinto[n-1][n-1] == 1) {
        return -1;  // Start o fine bloccati
    }
    
    // Direzioni: su, giù, sinistra, destra
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    // Matrice visitati
    bool **visitato = (bool**)malloc(n * sizeof(bool*));
    for (int i = 0; i < n; i++) {
        visitato[i] = (bool*)calloc(n, sizeof(bool));
    }
    
    // Coda per BFS (implementazione semplificata)
    Punto *queue = (Punto*)malloc(n * n * sizeof(Punto));
    int front = 0, rear = 0;
    
    // Aggiungi punto di partenza
    queue[rear++] = (Punto){0, 0, 0};
    visitato[0][0] = true;
    
    while (front < rear) {
        Punto curr = queue[front++];
        
        // Raggiunto destinazione?
        if (curr.x == n-1 && curr.y == n-1) {
            int dist = curr.dist;
            
            // Libera memoria
            for (int i = 0; i < n; i++) free(visitato[i]);
            free(visitato);
            free(queue);
            
            return dist;
        }
        
        // Esplora vicini
        for (int i = 0; i < 4; i++) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];
            
            // Controlla bounds e validità
            if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                !visitato[nx][ny] && labirinto[nx][ny] == 0) {
                
                visitato[nx][ny] = true;
                queue[rear++] = (Punto){nx, ny, curr.dist + 1};
            }
        }
    }
    
    // Nessun percorso trovato
    for (int i = 0; i < n; i++) free(visitato[i]);
    free(visitato);
    free(queue);
    
    return -1;
}

💪 Esercizio 8: Moltiplicazione di Catena di Matrici ESPERTO

Obiettivo: Date n matrici, trova l'ordine ottimale di moltiplicazione che minimizza il numero di operazioni.

Algoritmo: Programmazione dinamica - O(n³)

Esempio: A(10×30) × B(30×5) × C(5×60)
(A×B)×C = 10×30×5 + 10×5×60 = 4500
A×(B×C) = 30×5×60 + 10×30×60 = 27000

Soluzione:

/**
 * @brief Trova costo minimo per moltiplicare catena di matrici
 * @param dims Array di dimensioni: mat[i] ha dimensioni dims[i]×dims[i+1]
 * @param n Numero di matrici
 * @return Numero minimo di moltiplicazioni scalari
 */
int catena_matrici_dp(int *dims, int n) {
    // m[i][j] = costo minimo per moltiplicare matrici da i a j
    int **m = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        m[i] = (int*)calloc(n, sizeof(int));
    }
    
    // Lunghezza catena
    for (int len = 2; len <= n; len++) {
        // Punto iniziale
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            m[i][j] = INT_MAX;
            
            // Prova tutti i punti di split
            for (int k = i; k < j; k++) {
                // Costo = costo(i,k) + costo(k+1,j) + costo moltiplicazione finale
                int costo = m[i][k] + m[k+1][j] + 
                           dims[i] * dims[k+1] * dims[j+1];
                
                if (costo < m[i][j]) {
                    m[i][j] = costo;
                }
            }
        }
    }
    
    int risultato = m[0][n-1];
    
    // Libera memoria
    for (int i = 0; i < n; i++) free(m[i]);
    free(m);
    
    return risultato;
}

// Test
int main(void) {
    // Esempio: 3 matrici con dimensioni 10×30, 30×5, 5×60
    int dims[] = {10, 30, 5, 60};
    int n = 3;  // Numero di matrici
    
    int min_ops = catena_matrici_dp(dims, n);
    printf("Minimo numero di operazioni: %d\n", min_ops);
    
    return 0;
}

💪 Esercizio 9: Sudoku Solver ESPERTO

Obiettivo: Risolvi un Sudoku (matrice 9×9) usando backtracking.

Soluzione:

#define N 9

// Controlla se è sicuro mettere num in mat[row][col]
bool is_safe(int mat[N][N], int row, int col, int num) {
    // Controlla riga
    for (int x = 0; x < N; x++) {
        if (mat[row][x] == num) return false;
    }
    
    // Controlla colonna
    for (int x = 0; x < N; x++) {
        if (mat[x][col] == num) return false;
    }
    
    // Controlla box 3×3
    int start_row = row - row % 3;
    int start_col = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (mat[i + start_row][j + start_col] == num) {
                return false;
            }
        }
    }
    
    return true;
}

// Risolve Sudoku usando backtracking
bool risolvi_sudoku(int mat[N][N]) {
    int row, col;
    
    // Trova prossima cella vuota
    bool found = false;
    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (mat[row][col] == 0) {
                found = true;
                break;
            }
        }
        if (found) break;
    }
    
    // Se non ci sono celle vuote, Sudoku risolto
    if (!found) return true;
    
    // Prova numeri da 1 a 9
    for (int num = 1; num <= 9; num++) {
        if (is_safe(mat, row, col, num)) {
            mat[row][col] = num;
            
            // Ricorsione
            if (risolvi_sudoku(mat)) {
                return true;
            }
            
            // Backtrack
            mat[row][col] = 0;
        }
    }
    
    return false;  // Trigger backtracking
}

🎓 Suggerimenti per Padroneggiare le Matrici

  1. Pratica l'allocazione dinamica: Essenziale per matrici di dimensione variabile
  2. Ottimizza l'accesso: Sfrutta la località di memoria (row-major order)
  3. Usa algoritmi efficienti: O(n²⁸) di Strassen vs O(n³) standard
  4. Gestisci errori: Controlla sempre allocazioni e dimensioni
  5. Profila il codice: Usa Valgrind e gprof per trovare bottleneck
  6. Studia algoritmi avanzati: SVD, QR decomposition, metodi iterativi
  7. Pratica con LeetCode/HackerRank: Problemi su matrici sono comuni

📚 Risorse per Approfondire

  • Libri: "Introduction to Algorithms" (CLRS), "Numerical Linear Algebra" (Trefethen)
  • Librerie: BLAS, LAPACK, Eigen (C++), NumPy (Python)
  • Online: MIT OpenCourseWare (Linear Algebra), Khan Academy
  • Performance: Intel MKL, OpenBLAS per calcoli ottimizzati